package day4;

/**
 * 
 * 问题描述：
 * 荷兰国旗问题升级版本： 给定一个数组arr，和一个数num，
 * 请把小于num的数放在数组的左边，等于num的数放在数组的中间，
 * 大于num的数放在数组的右边。
 * 要求额外空间复杂度O(1)，时间复杂度O(N)
 * 
 * 解题思路：
 * 利用两个指针记录小于区和大于区两个区边界所在位置，比较当前数，根据情况进行分类：
 * 当前数大于分类标准的数，该数与大于区前一个数交换，指针向左移动；遇到小于
 * 分类标准数的时候，与左侧小于区域后一个数交换，指针向右移动；等于分类标准时，
 * 则遍历指针向前移动。
 * 
 */
public class FlagOfTheNetherlands2 {
    
    public static void solveProblem(int[] array,int flag){
        if(array==null||array.length<2){
            return;
        }

        int index=0;
        int leftIndex=0;
        int rightIndex=array.length-1;

        while(index<array.length&&index<=rightIndex){
            if(array[index]<flag){
                swap(array,leftIndex,index);
                index++;
                leftIndex++;
                continue;
            }
            
            if(array[index]>flag){
                swap(array, rightIndex, index);
                rightIndex--;
                continue;
            }

            if(array[index]==flag){
                index++;
                continue;
            }
        }
        
    }

    private static void swap(int[] array, int leftIndex, int i) {
        // array[leftIndex]=array[leftIndex]^array[i];
        // array[i]=array[leftIndex]^array[i];
        // array[leftIndex]=array[leftIndex]^array[i];
        //由于存在自己和自己进行了异或运算会变成零，故此处不能使用这种方式
        int temp=array[leftIndex];
        array[leftIndex]=array[i];
        array[i]=temp;
    }

    public static void main(String[] args){
        int[]  test=new int[]{4,6,8,5,3,9,7,6,0};
        solveProblem(test,5);
        for(int i=0;i<test.length;i++){
            System.out.println(test[i]);
        }
    }
}
